This paper explores the idea of knowledge-based security policies, whichare used to decide whether to answer a query over secret data based onan estimation of the querier's (possibly increased) knowledge given theresult. Limiting knowledge is the goal of existing information releasepolicies that employ mechanisms such as noising, anonymization, andredaction. Knowledge-based policies are more general: they increaseflexibility by not fixing the means to restrict information flow. Weenforce a knowledge-based policy by explicitly tracking a model of aquerier's belief about secret data, represented as a probabilitydistribution. We then deny any query that could increase knowledge abovea given threshold. We implement query analysis and belief tracking viaabstract interpretation using a novel domain we call probabilisticpolyhedra, whose design permits trading off precision with performancewhile ensuring estimates of a querier's knowledge are sound. Experimentswith our implementation show that several useful queries can be handledefficiently, and performance scales far better than would more standardimplementations of probabilistic computation based on sampling.
展开▼
